﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Ndo.Maths.MOP
{
    public class MOEA<Individual, Vector> : EA<Individual, Vector, Vector>
        where Individual : XY<Vector, Vector>, new()
        where Vector : class, IList<double>, ICloneable
    {

        public MOEA()
        {
            Crossover = new RandomOperation().Crossover;
            Mutation = new RandomOperation().BitMutation;
            Pick = new Tournament(this).Pick;//CreateBiasPicker();
        }

        public delegate DominationTypes DominationHandler(Vector a, Vector b);

        public enum DominationTypes
        {
            BeDominated = 0,
            Tie = 1,
            Dominate = 2,
            Equal = 3,
        }

        public CrowdingEvaluation<Vector> Evaluation = new CrowedingDistanceEvaluation<Vector>(Measure.EuclideanDistance);
        public DominationHandler Domination = NegativeDomination;
        #region Cache
        public abstract class DominationCacheBase
        {
            private DominationHandler domination;
            protected DominationCacheBase(DominationHandler domination)
            {
                this.domination = domination;
            }

            protected abstract bool GetCache(Vector a, Vector b, out DominationTypes dt);
            protected abstract void SetCache(Vector a, Vector b, DominationTypes dt);

            public DominationTypes Domination(Vector a, Vector b)
            {
                DominationTypes ret;
                if(GetCache(a, b, out ret))
                    return ret;
                ret = domination(a, b);
                SetCache(a, b, ret);
                return ret;
            }
        }
        public class DominationCache : DominationCacheBase
        {
            public DominationCache(DominationHandler domination)
                : base(domination)
            { }
            protected Dictionary<Pair<Vector>, DominationTypes> values = new Dictionary<Pair<Vector>, DominationTypes>();
            protected override bool GetCache(Vector a, Vector b, out DominationTypes dt)
            {
                if (ReferenceEquals(a, b))
                {
                    dt = DominationTypes.Equal;
                    return true;
                }
                return values.TryGetValue(new Pair<Vector>(a, b), out dt);
            }
            protected override void SetCache(Vector a, Vector b, DominationTypes dt)
            {
                if (ReferenceEquals(a, b))
                    return;
                int i = (int)dt;
                values[new Pair<Vector>(a, b)] = dt;
                if ((i & 1) == 0)
                {
                    i = 2 - i;
                }
                values[new Pair<Vector>(b, a)] = (DominationTypes)i;
            }
        }
        public class DominationCacheWithRelations : DominationCache
        {
            public DominationCacheWithRelations(DominationHandler domination)
                : base(domination)
            { }
            Dictionary<Vector, Dictionary<Vector, object>[]> relations = new Dictionary<Vector, Dictionary<Vector, object>[]>();
            protected override void SetCache(Vector a, Vector b, DominationTypes dt)
            {
                if (ReferenceEquals(a, b))
                    return;
                base.SetCache(a, b, dt);
                Dictionary<Vector, object>[] relation;
                int i = (int)dt;
                if ((i & 1) != 0)
                    return;
                if (!relations.TryGetValue(a, out relation))
                    relations[a] = relation = new Dictionary<Vector, object>[4];
                if (relation[i] == null)
                    relation[i] = new Dictionary<Vector, object>();
                relation[i].Add(b, null);
                //if ((i & 1) == 0)
                {
                    i = 2 - i;
                }
                if (!relations.TryGetValue(b, out relation))
                    relations[b] = relation = new Dictionary<Vector, object>[4];
                if (relation[i] == null)
                    relation[i] = new Dictionary<Vector, object>();
                relation[i].Add(a, null);
            }

            public ICollection<Vector>[] GetRelation(Vector a)
            {
                Dictionary<Vector, object>[] relation;
                relations.TryGetValue(a, out relation);
                if (relation == null)
                    return null;
                ICollection<Vector>[] ret = new ICollection<Vector>[4];
                for (int i = 0; i < 4; i++)
                    if (relation[i] != null)
                    {
                        ret[i] = relation[i].Keys;
                    }
                return ret;
            }

            public void Remove(Vector a)
            {
                Dictionary<Vector, object>[] relation;
                if (!relations.TryGetValue(a, out relation))
                    return;
                foreach (Dictionary<Vector, object> r1 in relation)
                {
                    foreach (Vector key in r1.Keys)
                    {
                        values.Remove(new Pair<Vector>(a, key));
                        values.Remove(new Pair<Vector>(key, a));
                        foreach (Dictionary<Vector, object> r2 in relations[key])
                        {
                            r2.Remove(a);
                        }
                    }
                }
            }
        }
        #endregion
        private static readonly bool[] DominateMap = new bool[] { false, false, true, false };
        private static readonly bool[] DominateWeaklyMap = new bool[] { false, false, true, true };
        private static readonly bool[] BeDominatedMap = new bool[] { true, false, false, false };
        private static readonly bool[] BeDominatedWeaklyMap = new bool[] { true, false, false, true };
        public bool Dominate(Vector a, Vector b)
        {
            return DominateMap[(int)Domination(a, b)];
        }
        public bool DominateWeakly(Vector a, Vector b)
        {
            return DominateWeaklyMap[(int)Domination(a, b)];
        }
        public bool BeDominated(Vector a, Vector b)
        {
            return BeDominatedMap[(int)Domination(a, b)];
        }
        public bool BeDominatedWeakly(Vector a, Vector b)
        {
            return BeDominatedWeaklyMap[(int)Domination(a, b)];
        }

        public static DominationTypes PositiveDomination(Vector a, Vector b)
        {
            for (int i = a.Count - 1; i >= 0; i--)
            {
                if (a[i] > b[i])
                {
                    while (--i >= 0)
                    {
                        if (a[i] < b[i])
                            return DominationTypes.Tie;
                    }
                    return DominationTypes.Dominate;
                }
                if (a[i] < b[i])
                {
                    while (--i >= 0)
                    {
                        if (a[i] > b[i])
                            return DominationTypes.Tie;
                    }
                    return DominationTypes.BeDominated;
                }
            }
            return DominationTypes.Equal;
        }

        public static DominationTypes NegativeDomination(Vector a, Vector b)
        {
            for (int i = a.Count - 1; i >= 0; i--)
            {
                if (a[i] < b[i])
                {
                    while (--i >= 0)
                    {
                        if (a[i] > b[i])
                            return DominationTypes.Tie;
                    }
                    return DominationTypes.Dominate;
                }
                if (a[i] > b[i])
                {
                    while (--i >= 0)
                    {
                        if (a[i] < b[i])
                            return DominationTypes.Tie;
                    }
                    return DominationTypes.BeDominated;
                }
            }
            return DominationTypes.Equal;
        }

        public int GetDominatingCount()
        {
            int count = 0;
            foreach (Individual individual in Population)
            {
                foreach (Individual individual1 in Population)
                {
                    if(!object.ReferenceEquals(individual1, individual))
                    {
                        if (Dominate(individual.Y, individual1.Y))
                            count++;
                    }
                }
            }
            return count;
        }

        public ICollection<Individual> GetNondominatedSet(IEnumerable<Individual> inds)
        {
            LinkedList<Individual> list = new LinkedList<Individual>();
            foreach (Individual i in inds)
            {
                bool good = true;
                for(LinkedListNode<Individual> node = list.First, p; node != null; )
                {
                    if (Dominate(node.Value.Y, i.Y))
                    {
                        good = false;
                        break;
                    }
                    else if (Dominate(i.Y, node.Value.Y))
                    {
                        node = (p = node).Next;
                        list.Remove(p);
                        continue;
                    }
                    node = node.Next;
                }
                if (good)
                    list.AddLast(i);
            }
            return list;
        }

        #region FitnessAssignment
        public delegate IList<Value> FitnessAssignmentHandler<Value>(IList<Individual> inds)
            where Value : IComparable<Value>;
        public static SelectionOperator FitnessAssignmentSelection<Value>(FitnessAssignmentHandler<Value> fa)
            where Value : IComparable<Value>
        {
            return new FA<Value>(fa).Selection;
        }
        private class FA<Value>
            where Value : IComparable<Value>
        {
            private FitnessAssignmentHandler<Value> fa;
            public FA(FitnessAssignmentHandler<Value> fa)
            {
                this.fa = fa;
            }
            public IList<Individual> Selection(IList<Individual> inds, int limit)
            {
                if (limit == 0)
                    return new Individual[0];
                if (limit > inds.Count)
                    limit = inds.Count;
                Value[] values = new Value[inds.Count];
                Individual[] keys = new Individual[inds.Count];
                fa(inds).CopyTo(values, 0);
                inds.CopyTo(keys, 0);
                Array.Sort(values, keys);
                Individual[] ret = new Individual[limit];
                Array.Copy(keys, 0, ret, 0, limit);
                return ret;
            }
        }
        #endregion

        #region BinaryPick
        public delegate Individual BinaryPickOperator(Individual i1, Individual i2);
        public static Individual ComparePick(Individual i1, Individual i2)
        {
            int a = Comparer<Individual>.Default.Compare(i1,i2);
            if(a==0)
                return null;
            return a < 0 ? i1 : i2;
        }
        public static BinaryPickOperator CreateRandomBinaryPicker()
        {
            return new RandomBinaryPicker().Pick;
        }
        private class RandomBinaryPicker
        {
            private Random rand = new Random();
            public Individual Pick(Individual i1, Individual i2)
            {
                return (rand.Next() & 1) == 0 ? i1 : i2;
            }
        }
        public static BinaryPickOperator CreateBinaryPicker(params BinaryPickOperator[] pickers)
        {
            return new BinaryPickers(pickers).Pick;
        }
        public static BinaryPickOperator CreateBinaryPickerEndWithRandom(params BinaryPickOperator[] pickers)
        {
            List<BinaryPickOperator> list = new List<BinaryPickOperator>(pickers);
            list.Add(new RandomBinaryPicker().Pick);
            return new BinaryPickers(pickers).Pick;
        }
        private class BinaryPickers
        {
            private IList<BinaryPickOperator> pickers;
            public BinaryPickers(IList<BinaryPickOperator> pickers)
            {
                this.pickers = pickers;
            }
            public Individual Pick(Individual i1, Individual i2)
            {
                foreach (BinaryPickOperator picker in pickers)
                {
                    Individual i = picker(i1, i2);
                    if (i != null)
                        return i;
                }
                return null;
            }
        }
        #endregion

        public class Tournament
        {
            public Tournament(MOEA<Individual, Vector> moea)
            {
                MOEA = moea;
            }

            public readonly MOEA<Individual, Vector> MOEA;
            private PickOperator randPick = CreateRandomPicker();
            public int ComparisionSetSize = 10;
            public Individual Pick(IList<Individual> inds)
            {
                Individual i1 = randPick(inds), i2 = randPick(inds);
                bool b1 = false, b2 = false;
                for (int i = 0; i < ComparisionSetSize && (!b1 || !b2) ; i++)
                {
                    Individual a = randPick(inds);
                    if (!b1)
                    {
                        b1 = MOEA.Dominate(a.Y, i1.Y);
                    }
                    if (!b2)
                    {
                        b2 = MOEA.Dominate(a.Y, i2.Y);
                    }
                }
                if(b1 == b2)
                {
                    return randPick(inds);
                }
                return b2 ? i1 : i2;
            }
        }
        #region DominateHandler
        //public delegate bool DominateHandler(Vector a, Vector b);
        //public static DominateHandler GetDominateHandler(DominationHandler domination)
        //{
        //    return new DominationHelper(domination, DominateMap).Dominate;
        //}
        //public static DominateHandler GetDominateWeaklyHandler(DominationHandler domination)
        //{
        //    return new DominationHelper(domination, DominateWeaklyMap).Dominate;
        //}
        //public static DominateHandler GetBeDominatedHandler(DominationHandler domination)
        //{
        //    return new DominationHelper(domination, BeDominatedMap).Dominate;
        //}
        //public static DominateHandler GetBeDominatedWeaklyHandler(DominationHandler domination)
        //{
        //    return new DominationHelper(domination, BeDominatedWeaklyMap).Dominate;
        //}

        //private class DominationHelper
        //{
        //    private DominationHandler domination;
        //    private bool[] map;
        //    public DominationHelper(DominationHandler domination, bool[] map)
        //    {
        //        this.domination = domination;
        //        this.map = map;
        //    }
        //    public bool Dominate(Vector a, Vector b)
        //    {
        //        return map[(int) domination(a, b) + 1];
        //    }
        //}
        public static bool LessThanOrEquals(Vector a, Vector b)
        {
            for (int i = a.Count - 1; i >= 0; i--)
            {
                if (a[i] > b[i])
                    return false;
            }
            return true;
        }
        public static bool LessThan(Vector a, Vector b)
        {
            double d = 0;
            for (int i = a.Count - 1; i >= 0; i--)
            {
                double dd = a[i] - b[i];
                if (dd > 0)
                    return false;
                d += dd;
            }
            return d < 0;
        }
        //public static bool GreaterThanOrEquals(Vector a, Vector b)
        //{
        //    for (int i = a.Count - 1; i >= 0; i--)
        //    {
        //        if (a[i] < b[i])
        //            return false;
        //    }
        //    return true;
        //}
        //public static bool GreaterThan(Vector a, Vector b)
        //{
        //    double d = 0;
        //    for (int i = a.Count - 1; i >= 0; i--)
        //    {
        //        double dd = a[i] - b[i];
        //        if (dd < 0)
        //            return false;
        //        d += dd;
        //    }
        //    return d > 0;
        //}
        #endregion
        protected class RefEqualityComparer : IEqualityComparer<Vector>
        {
            public bool Equals(Vector x, Vector y)
            {
                return ReferenceEquals(x, y);
            }

            public int GetHashCode(Vector obj)
            {
                return obj.GetHashCode();
            }
        }
        #region Crossover & Mutation
        public class RandomOperation
        {
            protected GaussianRandom grand = new GaussianRandom();
            protected Random rand = new Random();
            public virtual Vector InDoubleSpaceCrossover(Vector a, Vector b)
            {
                int m = a.Count;
                Vector c = (Vector)a.Clone();
                for (int i = 0; i < m; i++)
                {
                    double r = rand.NextDouble() * 2 - 1;
                    c[i] = (a[i] + b[i]) * 0.5 + (b[i] - a[i]) * r * Math.Pow(Math.Abs(r), m - 1);
                }
                return c;
            }
            public virtual Vector InSpaceCrossover(Vector a, Vector b)
            {
                int m = a.Count;
                Vector c = (Vector)a.Clone();
                for (int i = 0; i < m; i++)
                {
                    c[i] = a[i] + (b[i] - a[i]) * rand.NextDouble();
                }
                return c;
            }
            public virtual Vector SelectCrossover(Vector a, Vector b)
            {
                int m = a.Count;
                Vector c = (Vector)a.Clone();
                int r = 0;
                for (int i = 0; i < m; i++)
                {
                    int ii = i % 31;
                    if (ii == 0)
                        r = rand.Next();
                    c[i] = (r & (1 << ii)) == 0 ? a[i] : b[i];
                }
                return c;
            }
            public virtual Vector SelectOneInDoubleSpaceCrossover(Vector a, Vector b)
            {
                int m = a.Count;
                Vector c = (Vector)a.Clone();
                //int r = 0;
                //for (int i = 0; i < m; i++)
                //{
                //    int ii = i % 31;
                //    if (ii == 0)
                //        r = rand.Next();
                //    c[i] = (r & (1 << ii)) == 0 ? a[i] : b[i];
                //}
                int r = rand.Next(m);
                c[r] = (a[r] + b[r]) * 0.5 + (a[r] - b[r]) * (rand.NextDouble() * 2 - 1);
                return c;
            }
            public virtual Vector SelectOneInSpaceCrossover(Vector a, Vector b)
            {
                int m = a.Count;
                Vector c = (Vector)a.Clone();
                int r = rand.Next(m);
                c[r] = (a[r] + b[r]) * 0.5 + (a[r] - b[r]) * (rand.NextDouble() - 0.5);
                return c;
            }
            public virtual Vector Crossover(Vector a, Vector b)
            {
                return SelectOneInDoubleSpaceCrossover(a, b);
                switch (rand.Next(2))
                {
                    case 0:
                        return SelectOneInDoubleSpaceCrossover(a, b);
                    case 1:
                        return SelectCrossover(a, b);
                   default:
                        return InDoubleSpaceCrossover(a, b);
                }
                //int m = a.Count;
                //Vector c = (Vector)a.Clone();
                //double r = rand.NextDouble() * 2 - 1;
                ////r = r * Math.Pow(Math.Abs(r), m - 1) / 2;
                //for (int i = 0; i < m; i++)
                //{
                //    c[i] = (a[i] + b[i]) * 0.5 + (b[i] - a[i]) * r;
                //}
                //return c;
            }
            public virtual Vector Mutation(Vector a)
            {
                double r = rand.NextDouble();
                if (r > 0.5)
                    r = 1 / ((r - 0.5) * 2);
                else
                    r = r * r * 4;
                int i = rand.Next(a.Count * 2);
                if ((i & 1) == 0)
                    r = -r;
                Vector c = (Vector)a.Clone();
                c[i / 2] += r;
                return c;
            }
            public virtual Vector GMutation(Vector a)
            {
                Vector c = (Vector)a.Clone();
                int r = rand.Next();
                c[rand.Next(a.Count)] += grand.NextDouble();
                for (int i = 0; (r & (1 << i)) == 0 && i < 32; i++)
                {
                    c[rand.Next(a.Count)] += grand.NextDouble();
                }
                return c;
            }
            public virtual Vector RealMutation(Vector a)
            {
                Vector c = (Vector) a.Clone();
                int i = rand.Next(c.Count);
                double d = c[i];
                if(d == 0)
                    return c;
                while(true)
                {
                    int r = rand.Next(104*2) - 104;
                    if (r >= 0)
                        d += d*Math.Pow(2, 52-r - 1);
                    else
                        d -= d*Math.Pow(2, 52+r);
                    if (c[i] == d)
                        continue;
                    break;
                }
                c[i] = d;
                return c;
            }
            public virtual Vector BitMutation(Vector a)
            {
                Vector c = (Vector) a.Clone();
                int i = rand.Next(c.Count);
                double d;
                while(double.IsNaN(d = BitConverter.Int64BitsToDouble(BitConverter.DoubleToInt64Bits(c[i]) ^ (1L << rand.Next(64)))));
                c[i] = d;
                return c;
            }
        }

        public class RandomInitialization : RandomOperation
        {
            public readonly Vector lower;
            public readonly Vector upper;
            public RandomInitialization(Vector lower, Vector upper)
            {
                this.lower = lower;
                this.upper = upper;
            }

            public Vector Generate()
            {
                return InSpaceCrossover(lower, upper);
            }
        }
        #endregion

    }
}
